package algorithm.swordoff;

import java.util.PriorityQueue;

/**
 * 数据流中的中位数
 * 创建一个最小堆和最大堆,各自保存一半数字,其中最小堆的数字都不小于最大堆
 *    最小堆放较大的一半数字(这样一来过来一个数字就可以知道放到哪个堆里了),长度为N/2 (N为偶数) 或者 长度为(N+1)/2 (N为奇数)
 *    最大堆放较小的一半数字,长度为N/2 (N为偶数) 或者 长度为(N-1)/2 (N为奇数)
 *
 * 取中位数的API可以通过两个堆顶的元素求得,时间复杂度O(1)
 * 添加元素的时间复杂度O(logN)
 * 整体空间复杂度O(N)
 *
 * 注意: 数据流必须是有限的,如果数据流是无界或者无限的数据流,则在一般情况下是无解的
 * 考虑一个最大容量为N的设备,和一个已经流逝过的数据流恰好到达了设备的容量上限,即流过的数据个数为N
 * 不妨设中位数位置为n,显然1<=n<=N,
 * 存在这这样的情况,再来一个数据,此时流过的数据个数为N+1,容器将挤出一个最值,不妨设挤出的值为最大值
 * 此时继续来N个比这个最大值还大的数,此时的中位数应该是被挤出去的这个数,然是容器已经丢失了这个数字无法再获取它作为中位数了
 *
 * 一般地,如果挤出去的值位置在第n个,总有办法可以填充一组后续进入的数据使得中位数是丢失的这个数据
 *
 * 举个例子,N=3,流过的数据为1,2,3
 * 此时来一个2,容器可容纳的数字为1,2,2，3被挤掉
 * 再来3个4,原始数据是1,2,2,3,4,4,4,中位数是3已经被丢失
 */


public class SQ41 {

    static class MedianFinder {

        PriorityQueue<Integer> minHeap;
        PriorityQueue<Integer> maxHeap;

        /** initialize your data structure here. */
        public MedianFinder() {
            minHeap = new PriorityQueue<>((o1, o2) -> o1-o2);
            maxHeap = new PriorityQueue<>((o1, o2) -> o2-o1);
        }

        // 核心在这个方法:如果两个堆相等,那么应该添加到最小堆,但是这里先添加到最大堆,让最大堆排序挤出一个最小的再放回最小堆,另一种情况同理
        public void addNum(int num) {
            if (minHeap.size() == maxHeap.size()) {
                maxHeap.add(num);
                minHeap.add(maxHeap.poll());
            }

            else {
                minHeap.add(num);
                maxHeap.add(minHeap.poll());
            }

        }

        public double findMedian() {
            if (minHeap.size() > maxHeap.size()) return minHeap.peek();
            else if (minHeap.size() == 0) return 0.0;
            else return 0.5*(minHeap.peek() + maxHeap.peek());
        }
    }

    public static void main(String[] args) {
        MedianFinder medianFinder = new MedianFinder();
        medianFinder.addNum(1);
        medianFinder.addNum(2);
        medianFinder.addNum(3);
        System.out.println(medianFinder.findMedian());
    }

}
